0001 // 0002 // BigUInt Exponentiation.swift 0003 // BigInt 0004 // 0005 // Created by Károly Lőrentey on 2016-01-03. 0006 // Copyright © 2016 Károly Lőrentey. All rights reserved. 0007 // 0008 0009 import Foundation 0010 0011 extension BigUInt { 0012 //MARK: Exponentiation 0013 0014 /// Returns this integer raised to the power `exponent`. 0015 /// 0016 /// This function calculates the result by [successively squaring the base while halving the exponent][expsqr]. 0017 /// 0018 /// [expsqr]: https://en.wikipedia.org/wiki/Exponentiation_by_squaring 0019 /// 0020 /// - Note: This function can be unreasonably expensive for large exponents, which is why `exponent` is 0021 /// a simple integer value. If you want to calculate big exponents, you'll probably need to use 0022 /// the modulo arithmetic variant. 0023 /// - Returns: 1 if `exponent == 0`, otherwise `self` raised to `exponent`. (This implies that `0.power(0) == 1`.) 0024 /// - SeeAlso: `BigUInt.power(_:, modulus:)` 0025 /// - Complexity: O((exponent * self.count)^log2(3)) or somesuch. The result may require a large amount of memory, too. 0026 @warn_unused_result 0027 public func power(exponent: Int) -> BigUInt { 0028 if exponent == 0 { return 1 } 0029 if exponent == 1 { return self } 0030 if self.count <= 1 && self[0] <= 1 { return self } 0031 var result = BigUInt(1) 0032 var b = self 0033 var e = exponent 0034 while e > 0 { 0035 if e & 1 == 1 { 0036 result = (result * b) 0037 } 0038 e >>= 1 0039 b = (b * b) 0040 } 0041 return result 0042 } 0043 0044 /// Returns the remainder of this integer raised to the power `exponent` in modulo arithmetic under `modulus`. 0045 /// 0046 /// Uses the [right-to-left binary method][rtlb]. 0047 /// 0048 /// [rtlb]: https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method 0049 /// 0050 /// - Complexity: O(exponent.count * modulus.count^log2(3)) or somesuch 0051 @warn_unused_result 0052 public func power(exponent: BigUInt, modulus: BigUInt) -> BigUInt { 0053 if modulus == 1 { return 0 } 0054 var result = BigUInt(1) 0055 var b = self % modulus 0056 var e = exponent 0057 while e > 0 { 0058 if e[0] & 1 == 1 { 0059 result = (result * b) % modulus 0060 } 0061 e >>= 1 0062 b = (b * b) % modulus 0063 } 0064 return result 0065 } 0066 } 0067
BigUInt Prime Test.swift:49